﻿#include <iostream>
#include <stack>

using namespace std;

template <class T>
class QueueByStack
{
public:
    void push(T t);
    T pop();

private:
    stack<T> stack1;
    stack<T> stack2;
};

template <class T>
void QueueByStack<T>::push(T t)
{
    stack1.push(t);
}

template <class T>
T QueueByStack<T>::pop()
{
    if (stack1.empty()) return NULL;

    T top;
    while (stack1.size() > 1)
    {
        top = stack1.top();
        stack1.pop();
        stack2.push(top);
    }

    auto res = stack1.top();
    stack1.pop();

    while (!stack2.empty())
    {
        top = stack2.top();
        stack2.pop();
        stack1.push(top);
    }

    return res;
}

/**
 * 用栈模拟队列
 */
int main_UseStackToMakeQueue()
{
    int numbers[] = {1,2,3,4,5,6};
    int size = sizeof(numbers) / sizeof(int);
    QueueByStack<int> q;
    for (int i = 0; i < size; i++)
    {
        q.push(numbers[i]);
    }

    for (int i = 0; i < size; i++)
    {
        printf("[%d]=%d\n", i, q.pop());
    }

    return 0;
}